import java.util.ArrayList;
import java.util.List;

public class Solution229 {
    public List<Integer> majorityElement(int[] nums) {
        int a = 0, b = 0, ac = 0, bc = 0;
        for (int num : nums) {
            if (a == num) {
                ac++;
            } else if (b == num) {
                bc++;
            } else if (ac == 0) {
                a = num;
                ac++;
            } else if (bc == 0) {
                b = num;
                bc++;
            } else {
                ac--;
                bc--;
            }
        }
        ac = bc = 0;
        for (int num : nums) {
            if (num == a) {
                ac++;
            } else if (num == b) {
                bc++;
            }
        }
        int m = nums.length / 3;
        List<Integer> res = new ArrayList<>();
        if (ac > m) {
            res.add(a);
        }
        if (bc > m) {
            res.add(b);
        }
        return res;
    }
}

